package com.example.tree.dp;

import com.example.tree.TreeNode;

/**
 * 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
 *  选择二叉树中 任意 节点和一个方向（左或者右）。
 *  如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
 *  改变前进方向：左变右或者右变左。
 *  重复第二步和第三步，直到你在树中无法继续移动。
 *  交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
 *
 *  请你返回给定树中最长 交错路径 的长度。
 *  示例 1：
 *  输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
 * 输出：3
 * 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
 *
 *  示例 2：
 *  输入：root = [1,1,1,null,1,null,null,1,1,null,1]
 * 输出：4
 * 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
 *
 *  示例 3：
 *  输入：root = [1]
 * 输出：0
 */
public class Leetcode1372_LongestZigZag {
    static class Solution {
        /**
         * endLeft, endRight = dfs(node) 代表状态如下：
         *     endLeft表示以node节点为结尾的以左向为停止的交错路径的长度
         *     endRight表示以node节点为结尾的以右向为停止的交错路径的长度
         * 使用res表示最终结果，每算完一个节点的结果，尝试更新res
         * @param root
         * @return
         */
        public int longestZigZag(TreeNode root) {
            int[] res = {0};
            class Stub {
                int[] dfs(TreeNode node) {
                    if (node == null) return new int[] {0, 0};
                    int[] leftRes = dfs(node.left);
                    int[] rightRes = dfs(node.right);
                    if (node.left != null) leftRes[1] += 1;
                    if (node.right != null) rightRes[0] += 1;
                    res[0] = Math.max(res[0], Math.max(Math.max(leftRes[0], leftRes[1]),Math.max(rightRes[0], rightRes[1])));
                    return new int[] {leftRes[1], rightRes[0]};
                }
            }
            new Stub().dfs(root);
            return res[0];
        }
    }

    public static void main(String[] args) {
        //  1
        //      1
        //   1      1
        //        1    1
        //          1
        //            1
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(); root.right.right = new  TreeNode(1);
        root.right.right.left = new TreeNode(1); root.right.right.right = new TreeNode(1);
        root.right.right.left.right = new TreeNode(1);
        root.right.right.left.right.right = new TreeNode(1);
        System.out.println(new Solution().longestZigZag(root));
    }
}
